/*
 * algorithm.h
 *
 *  Created on: Sep 8, 2008
 *      Author: lindenb
 */


#ifndef UTIL_ALGORITHM_HEADER
#define UTIL_ALGORITHM_HEADER
#ifdef  __cplusplus
extern "C" {
#endif

#include "lang/morestddef.h"
/**
 * Lower_bound is a version of binary search:
 * it attempts to find the element value in an ordered range [base, base+nmembers)
 * Specifically, it returns the first position where value could be inserted without
 * violating the ordering.
 */
extern int lower_bound(
		Ptr base,
		size_t nmembers,
		size_t item_size,
		int(*compar)(const Ptr, const Ptr),
		Ptr key
		);
/**
 *  Finds the last position in which keyl could be inserted
 *  without changing the ordering.
 *
 */
extern int upper_bound(
		BytePtr base,
		size_t nmembers,
		size_t item_size,
		int(*compar)(const void *, const void *),
		BytePtr key
		);

#ifdef  __cplusplus
}
#endif

#endif /* UTIL_ALGORITHM_HEADER */
